// 贪心哈希
package main

func main() {
	roman := intToRoman(3749)
	println(roman)
}

func intToRoman(num int) string {
	res := ""
	// 注意map[int]string{1000:"M",900:"CM"}这不是有序hash
	// 有序hash的变相构造实现
	var mps = []struct {
		k int
		v string
	}{
		{1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
		{100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
		{10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"},
		{1, "I"},
	}
	for _, mp := range mps {
		for mp.k <= num {
			num -= mp.k
			res += mp.v
		}
	}
	return res
}
